import java.util.*;

public class t1477 {

    //1477. 找两个和为目标值且不重叠的子数组 中等
    public static void main(String[] args) {
        int arr[] = {2, 1, 3, 3, 4, 4, 4, 2, 3, 1};
        int target = 6;
        System.out.println(minSumOfLengths(arr, target));
    }
    //动态规划+滑动窗口（双指针）
    public static int minSumOfLengths(int[] arr, int target) {
        int len = arr.length;
        int dp[] = new int[len];
        //dp保存以j结尾的连续和为target的最小长度
        int sum = 0;
        int ans = Integer.MAX_VALUE / 2;
        Arrays.fill(dp, Integer.MAX_VALUE / 2);
        for (int i = 0, j = 0; j < len; j++) {
            sum += arr[j];
            while (i <= j && sum > target) {
                sum -= arr[i++];
            }
            if(sum == target){
                dp[j] = j-i+1;
                if(i!=0){
                    ans = Math.min(ans,dp[i-1]+j-i+1);
                }
            }
            if(j!=0){
                dp[j] = Math.min(dp[j],dp[j-1]);
            }
        }
        return ans>len?-1:ans;
    }


//            int n = arr.length;
//            int[] dp = new int[n];
//            // 注意不能设置为最大值，因为相加会溢出
//            Arrays.fill(dp, Integer.MAX_VALUE / 2);
//
//            int ans = Integer.MAX_VALUE;
//            for(int i = 0, j = 0, sum = 0; j < n; j++){
//                sum += arr[j];
//                while(i <= j && sum > target){//这里保证要么i与j重合 要么
//                    sum -= arr[i++];
//                }
//                // 找到满足条件的一个区间
//                if(sum == target){
//                    dp[j] = j - i + 1;
//                    if(i != 0){
//
//                        ans = Math.min(ans, dp[i-1] + j - i + 1);
//                    }
//                }
//                if(j != 0)
//                    dp[j] = Math.min(dp[j], dp[j-1]);//保证当前dp维护的永远是最小区间
//            }
//
//            return ans > arr.length ? -1 : ans;

}


